#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "lnklist.h"

int listhead_init(list_t **li, int size)
{
	list_t *me = NULL;

	me = malloc(sizeof (list_t));
	if (NULL == me)
		return -1;
	me->size = size; // 每个数据元素的size
	me->node.next = NULL;
	me->node.data = NULL;

	*li = me;

	return 0;
}

static node_t *__alloc_node(int size, const void *data)
{
	node_t *new_node;

	new_node = malloc(sizeof (node_t));
	if (NULL == new_node)
		return NULL;
	new_node->data = malloc(size);
	if (NULL == new_node->data) {
		free(new_node);
		new_node = NULL;
		return NULL;
	}
	memcpy(new_node->data, data, size);
	new_node->next = NULL;

	return new_node;
}

int list_empty(const list_t *li)
{
	return li->node.next == NULL;
}

int list_insert_head(list_t *li, const void *data)
{
	node_t *n = __alloc_node(li->size, data);
	if (NULL == n)
		return -1;
	n->next = li->node.next;
	li->node.next = n;

	return 0;
}

int list_insert_tail(list_t *li, const void *data)
{
	node_t *pos;
	node_t *n = __alloc_node(li->size, data);
	if (NULL == n)
		return -1;
	if (list_empty(li)) {
		pos = &li->node;
	} else {
		for (pos = li->node.next; pos->next != NULL; pos = pos->next) {
			;
		}
	}
	pos->next = n;

	return 0;
}

static node_t *__prev_node(const list_t *li, const void *key, cmp_t cmp)
{
	node_t *prev = NULL;

	for (prev = (node_t *) &li->node; prev->next != NULL; prev = prev->next) {
		if (0 == cmp(prev->next->data, key))
			return prev;
	}

	return NULL;
}

void *list_find(const list_t *li, const void *key, cmp_t cmp)
{
	node_t *prev;

	prev = __prev_node(li, key, cmp);
	if (NULL == prev)
		return NULL;
	return prev->next->data;
}

int list_delete(list_t *li, const void *key, cmp_t cmp)
{
	node_t *prev, *del;

	prev = __prev_node(li, key, cmp);
	if (NULL == prev)
		return -1;
	del = prev->next;
	prev->next = del->next;
	del->next = NULL;
	free(del->data);
	del->data = NULL;
	free(del);
	del = NULL;

	return 0;
}

void list_travel(const list_t *li, pri_t pri)
{
	node_t *cur = NULL;

	for (cur = li->node.next; cur != NULL; cur = cur->next) {
		pri(cur->data);

		//printf(" (%p)\n", cur);
	}
}

// 始终返回0,即始终判定相等
static int __always_cmp(const void *data, const void *key)
{
	return 0;
}

void list_destroy(list_t **li)
{
	while (!list_empty(*li)) {
		list_delete(*li, NULL, __always_cmp);
	}
	free(*li);
	*li = NULL;
}

// Extra

void *list_middle(list_t *li)
{
	node_t* fast = li->node.next;
	node_t* slow = li->node.next;

	while (fast != NULL) {
		fast = fast->next;
		if (fast != NULL) {
			// 还没走到头，再走一步
			fast = fast->next;
			// 要是fast没走到头slow再继续走，走到头的话slow就别走了
			slow = slow->next;
		}
		printf("Fast: %p Slow: %p\n", fast, slow);
	}

	return slow;
}

void list_reverse(list_t *li)
{
	node_t *p = NULL;
	node_t *n;
	node_t *cur = li->node.next;

	while (cur != NULL) {
		n = cur->next;
		cur->next = p;
		p = cur;
		cur = n;

		// 更新头节点中的首地址
		if (cur != NULL) {
			li->node.next = cur;
		}
	}
}

